package common.test;

import common.TreeNode;

/**
 * 124. 二叉树中的最大路径和
 */
public class _124_MaxPathSum {

    int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        pathSum(root);
        return ans;
    }


    public int pathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = pathSum(root.left);
        int r = pathSum(root.right);
        int currPath = Math.max(root.val, Math.max(l + root.val, r + root.val));
        ans = Math.max(ans, Math.max(l + r + root.val, currPath));
        return currPath;
    }
}
